package com.hdu.other.monotonyQueue;

public class lc1438 {

    static class Solution {

        private static final int MAX_N = 100000;
        private static final int[] MAX_Q = new int[MAX_N];
        private static final int[] MIN_Q = new int[MAX_N];

        private static int MAX_H, MAX_T = 0;
        private static int MIN_H, MIN_T = 0;

        public int longestSubarray(int[] nums, int limit) {
            refresh();
            int n = nums.length;
            int l = 0, r = 0;
            int ans = 0;
            while (r < n) {
                add(nums, r);
                while (MAX_H < MAX_T && MIN_H < MIN_T && max(nums) - min(nums) > limit) delete(l++);
                ans = Math.max(
                        ans,
                        r - l + 1
                );
                r++;
            }
            return ans;
        }

        void add(int[] nums, int index) {
            while (MAX_H < MAX_T && nums[index] > nums[MAX_Q[MAX_T - 1]]) MAX_T--;
            while (MIN_H < MIN_T && nums[index] < nums[MIN_Q[MIN_T - 1]]) MIN_T--;
            MAX_Q[MAX_T++] = index;
            MIN_Q[MIN_T++] = index;
        }

        int max(int[] nums) {
            return nums[MAX_Q[MAX_H]];
        }

        int min(int[] nums) {
            return nums[MIN_Q[MIN_H]];
        }

        void delete(int index) {
            if (MIN_Q[MIN_H] == index) MIN_H++;
            if (MAX_Q[MAX_H] == index) MAX_H++;
        }


        static void refresh() {
            MAX_H = MAX_T = MIN_H = MIN_T = 0;
        }
    }

}
